package com.practice.merge;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

public class Solution2 {
	public static void main(String[] args) {
		Solution2 s = new Solution2();
		ArrayList<ArrayList> lists = s.read();
		ArrayList<Integer> merged = s.merge(lists);
		for (int i : merged) System.out.print(i + " ");
		System.out.println();
	}
	
	private ArrayList<ArrayList> read() {
		ArrayList<ArrayList> lists = new ArrayList<ArrayList>();
		ArrayList<Integer> numbers = new ArrayList<Integer>();
		try {
			BufferedReader f = new BufferedReader(new FileReader("src/test/resources/merge.txt"));
			String line = null;
			while ((line = f.readLine()) != null) {
				String[] t = line.split(" ");
				for (String s : t) {
					s = s.trim();
					if (s.length() > 0) {
						try {
							numbers.add(Integer.parseInt(s));
						} catch (NumberFormatException e) {
							// TODO Auto-generated catch block
							e.printStackTrace();
						}
					}
				}
			}
			
			for (int i=0; i<numbers.size();) {
				ArrayList<Integer> list = new ArrayList<Integer>();
				int n = numbers.get(i);
				i++;
				for (; n>0; n--, i++) {
					list.add(numbers.get(i));
				}
				Collections.sort(list);
				if (list.size() > 0) lists.add(list);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		return lists;
	}
	
	public ArrayList<Integer> merge(ArrayList<ArrayList> lists) {
		PriorityQueue<Pair> queue = new PriorityQueue<Pair>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for (int i=0; i<lists.size(); i++) {
			ArrayList<Integer> l = lists.get(i);
			if (l.size() > 0) {
				queue.add(new Pair(l.get(0), i));
			}
		}
		
		while (!queue.isEmpty()) {
			Pair p = queue.remove();
			list.add(p.value);
			ArrayList<Integer> l = lists.get(p.index);
			if (l.size() > p.index+1) {
				queue.add(new Pair(l.get(p.index+1), p.index));
			}
		}
		
		return list;
	}
	
	private class Pair implements Comparable {
		int value;
		int index;
		public Pair(int value, int index) {
			this.value = value;
			this.index = index;
		}
		
		public int compareTo(Object p) {
			return this.value - ((Pair)p).value; 
		}
	}
}
